#include "testlib.h"

/*Shuffle all elements in a vector.*/
template<class T>
void shuffle(std::vector<T> &v) {
    shuffle(v.begin(), v.end());
}

template<class T>
T rndIn(const std::vector<T> &v) {
    return v[rnd.next(v.size())];
}

template<class T>
std::vector<T> rndIn(const std::vector<T> &v, int k) {
    if(v.size() < k)
        __testlib_fail("Elements less than expected");
    std::vector<T> ret = v;
    shuffle(ret);
    ret.resize(k);
    return ret;
}

/*Print both elements in a single line of a pair.*/
template<typename A, typename B>
void println(const std::pair<A, B> &p) {
    __testlib_print_one(p.first);
    std::cout << " ";
    __testlib_print_one(p.second);
    std::cout << std::endl;
}

/*Random permutation of [base, base + length - 1] that make random swaps several times.
use reversed permutation if times < 0.
*/
template<class T>
std::vector<T> genPerm(int length, T base, int times) {
    std::vector<T> ret(length);
    for(int i = 0; i < length; i ++)
        ret[i] = i + base;
    if(times < 0) {
        times = -times;
        reverse(ret.begin(), ret.end());
    }
    

    if(times <= 2 * length)
        for(int i = 0; i < times; i ++) {
            int a = rnd.next(length), b = rnd.next(length);
            std::swap(ret[a], ret[b]);
        }
    else
        shuffle(ret);

    return ret;
}

/*Random permutation of [0, length - 1] that make random swaps several times.
use reversed permutation if times < 0.
*/
std::vector<int> genPerm(int length, int times) {
    return genPerm(length, 0, times);
}

/*Generate a tree of n vertices, return a vector of n - 1 edges as pairs.*/
std::vector<std::pair<int, int>> genTree(int n, int t)
{

    std::vector<int> p(n);
    for(int i = 0; i < n; i ++)
        if (i > 0)
            p[i] = rnd.wnext(i, t);

    std::vector<int> perm = genPerm(n, 1, 1000000000);
    std::vector<std::pair<int,int> > edges;

    for (int i = 1; i < n; i++)
        if (rnd.next(2))
            edges.push_back({perm[i], perm[p[i]]});
        else
            edges.push_back({perm[p[i]], perm[i]});

    shuffle(edges.begin(), edges.end());

    return edges;
}

template <class T>
std::vector<T> genSeq(int len, T l, T r, double t, double w) {
    std::vector<T> v(len);
    for(int i = 0; i < len; i ++)
        v[i] = rnd.wnext(l, r, t * i + w);
    return v;
}


std::vector<int> getPrimes(int n) {
    std::vector<bool> isPrime(n, true);
    std::vector<int> primes;
    for(int i = 2; i <= n; i ++) {
        if(isPrime[i]) primes.push_back(i);
        for(auto j : primes) {
            if((long long)i * j > n) break;
            isPrime[i * j] = false;
            if(i % j == 0) break;
        }
    }
    return primes;
}

std::vector<std::pair<int, int> > genDirectedGraph(int n, int m) {
    std::vector<std::pair<int, int> > ret;
    if((long long)n * n < 10000000ll) {
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                if(i != j) ret.push_back({i, j});
        shuffle(ret);
        ret.resize(m);
    }else{
        std::set<std::pair<int, int> > s;
        for(int i = 0; i < m; i ++) {
            int u = rnd.next(1, n), v = rnd.next(1, n);
            while(u == v || s.count({u, v})) u = rnd.next(1, n), v = rnd.next(1, n);
            s.insert({u, v});
        }
        ret = std::vector<std::pair<int, int> >(s.begin(), s.end());
    }
    return ret;
}

std::vector<std::pair<int, int> > genDAG(int n, int m) {
    std::vector<std::pair<int, int> > ret;
    std::vector<int> p(n);
    for(int i = 0; i < n; i ++)
        p[i] = i + 1;
    shuffle(p);
    if((long long)n * n < 10000000ll) {
        for(int i = 0; i < n; i ++)
            for(int j = i + 1; j < n; j ++)
                ret.push_back({p[i], p[j]});
        shuffle(ret);
        ret.resize(m);
    }else{
        std::set<std::pair<int, int> > s;
        for(int i = 0; i < m; i ++) {
            int u = rnd.next(n), v = rnd.next(n);
            if(u > v) std::swap(u, v);
            while(u == v || s.count({p[u], p[v]})) {
                u = rnd.next(1, n), v = rnd.next(1, n);
                if(u > v) std::swap(u, v);
            }
            s.insert({p[u], p[v]});
        }
        ret = std::vector<std::pair<int, int> >(s.begin(), s.end());
    }
    return ret;
}

std::vector<std::pair<int, int> > genUndirected(int n, int m) {
    return genDAG(n, m);    
}

std::vector<std::pair<int, int> > genConnectedGraph(int n, int m, int t) {
    if(m < n - 1) {
        std::cerr << "FAIL\n";
    }
    std::vector<std::pair<int, int> > tree = genTree(n, t), ret;
    m -= n - 1;
    sort(tree.begin(), tree.end());
    if((long long)n * n < 10000000ll) {
        for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++)
                if(i != j && !binary_search(tree.begin(), tree.end(), std::pair<int, int>(i, j))
                          && !binary_search(tree.begin(), tree.end(), std::pair<int, int>(j, i))) ret.push_back({i, j});
        shuffle(ret);
        ret.resize(m);
        ret.insert(ret.end(), tree.begin(), tree.end());
    }else{
        std::set<std::pair<int, int> > s(tree.begin(), tree.end());
        for(int i = 0; i < m; i ++) {
            int u = rnd.next(1, n), v = rnd.next(1, n);
            while(u == v || s.count({u, v}) || s.count({v, u})) u = rnd.next(1, n), v = rnd.next(1, n);
            s.insert({u, v});
        }
        ret = std::vector<std::pair<int, int> >(s.begin(), s.end());
    }
    return ret;
}

std::vector<std::pair<int, int> > genConnectedGraph(int n, int m) {
    return genConnectedGraph(n, m, rnd.next(-n, n));
}

std::string genString(std::string base, int length, int dirt) {
    std::string S = base/*.substr(rnd.next(base.length()), 1)*/;
    while(S.length() < length) {
        S += S;
        for(int j = dirt; j < S.length(); j += dirt)
            S[rnd.next(S.length())] = base[rnd.next(base.length())];
    }
    return S.substr(0, length);
}

std::vector<int> randomDistribute(int n, int x, int z) {
    std::vector<int> ret(n, z);
    for(int i = z * n; i < x; i ++)
        ret[rnd.next(n)] ++;
    return ret;
}


/*Generate a list of t integers greater or equal to x and sum to be n that used as testcases.
*/
std::vector<int> splitTestcases(int t, int n, int x) {
    std::vector<int> ret(t, x);
    int left = n - t * x;
    if(left < 0) {
        quit(_fail, "invalid parameters for testcases.");
        return ret;
    }
    ret[rnd.next(t)] += left / 2;
    left -= left / 2;
    for(int i = 0; i < left; i ++) {
        ret[rnd.next(t)] ++;
    }
    return ret;
}